package leetcode_700;

import java.util.HashMap;
import java.util.HashSet;

/**
 *@author 周杨
 *MapSumPairs_677 实现一种map 可以存入一种前缀和int 查询问 以这种前缀开头的单词的数量
 *describe:用前缀树 AC 20%
 *2018年10月6日 下午3:57:42
 */
public class MapSumPairs_677 {
	HashSet<String> set ;
	class TrieNode{
	    int count;
	    HashMap<Character, TrieNode> childNode = new HashMap<>();
	}
	TrieNode root;
	/** Initialize your data structure here. */
	public MapSumPairs_677() {
	   root = new TrieNode(); 
	    set = new HashSet<>();
	}

	public void insert(String key, int val) {
	  
	    TrieNode curr = root;
	    int len = key.length();
	    if(!set.contains(key)){
	      for(int i = 0; i < len; i++){
	        char c = key.charAt(i);
	        if(!curr.childNode.containsKey(c))
	        {
	            curr.childNode.put(c,new TrieNode());
	        }
	        curr = curr.childNode.get(c);
	        curr.count += val;
	        }  
	    }else{
	            for(int i = 0; i < len; i++){
	                char c = key.charAt(i);
	                 if(!curr.childNode.containsKey(c))
	                    {
	                     curr.childNode.put(c,new TrieNode());
	                    }
	            curr = curr.childNode.get(c);
	            curr.count = val;
	            }
	        }
	    set.add(key);
	}

	public int sum(String prefix) {
	    
	     TrieNode curr = root;
	    int len = prefix.length();
	    
	    for(int i = 0; i < len; i++)
	    {
	        char c = prefix.charAt(i);
	        if(!curr.childNode.containsKey(c))
	        {
	            return 0;
	        }
	        curr = curr.childNode.get(c);
	    }
	    
	    return curr.count;
	}
}
